1. Field of the Invention
The present invention relates to a technique where stack allocation is performed on the basis of the result of an escape analysis in a computer system.
2. Description of the Related Art
The process of allocating a task object not to a heap but to a stack on the basis of an escape analysis has been performed in computer systems. Specifically, by allocating an object not to a heap but to a stack if possible, the cost of garbage collection or heap allocation can be reduced.
JSR 166 of Java® 7 is provided with a Fork-Join framework proposed by Doug Lea. For the Fork-Join framework, see Doug Lea, “A Java fork/join framework,” Java Grande Conference archive, Proceedings of the ACM 2000 conference on Java Grande table of contents, pages 36-43, 2000.
Specifically, the Fork-Join framework is a mechanism for creating an object for a task (task object) and realizing divide and conquer using fork( ) and join( ). That is, a task is recursively divided into subtasks until it becomes small enough to be solved using a simple and short sequential method.
Fork( ) is a function of starting a task. The thread for executing the task may be a thread other than the thread which has called the fork. Join( ) is a function of waiting for the completion of the forked task. Hereafter, a thread for executing a task will be referred to as a “worker.”
In the implementation of Java® 7, a work stealing mechanism is used to implement the above-mentioned framework. Specifically, each worker is assigned a task queue specific to the worker. When starting the task of a task object created in a function using fork( ), the task object is temporarily put into the task queue of the worker which has executed fork( ). Here assume that the worker which has performed fork( ) on the task object waits for the completion of the task object using join( ), If any other worker has yet to process the task object; the worker processes the task object; if any other worker is processing it, the worker waits for the completion of the processing. Each worker, when completing the processing of the current task, extracts a task from the assigned task queue and starts processing it and, when completing the processing of all tasks in the task queue (idle state), extracts a task from the task queue of any other worker (steal) and processes it. For each worker to process a task contained in a task queue other than the assigned task queue is called “work stealing.”
Shown below is an example of execution of a parallel execution program implementing work stealing.
class Fib extends ForkJoinTask {Integer r;Fib(int r) { this.r = r; 3333}protected boolean exec( ) {if (r < 2) return true;Fib f1 = new Fib(r − 1);Fib f2 = new Fib(r − 2);f1.fork( ); f2.fork( );f2.join( ); f1.join( );r = f1.r + f2.r;return true;}}void main( ) {pool.invoke(new Fib(5));}
The execution process of this program is as follows:
First, a task object (ForkJoinTask) is created using Fib f1=new Fib(r−1) and Fib f2=new Fib(r−2).
Second, a worker calls fork( ) of the task object using f1.fork( ) and f2.fork( ). The worker then inserts the task object into the task queue specific to the worker. If any other worker is idle, the task object is stolen from the queue by the idle worker.
Third, the worker which has called fork( ) calls join( ) of the task object using f2.join( ) and f1.join( ) and waits for the completion of the task. If the task object is not stolen, the worker which has called join( ) extracts the task object from the task queue specific to the worker and performs processing (exec( )) of the task. If the task object is stolen, the worker waits for the completion of the processing (exec( )) of the task object.
In this process, an attempt to realize fine-grained parallelism causes creation of a great number of task objects. Objects which are used only through the field of a task object are also created in a great number. This increases the cost of heap allocation of the task object and the associated garbage collection cost, increasing the runtime cost. To resolve this, the task object may be allocated to the stack. However, the task object is inserted into a queue on the heap in the fork( ) processing. Since the object on the heap can basically be referred to (escape) by other threads, an ordinary escape analysis does not determine that stack allocation is possible.
Japanese Unexamined Patent Application Publication No. 2003-15876 relates to a system and method that can allocate an object to a method call stack in a partial compilation environment and discloses a technique where when dynamically loading a class in Java®, an escape analysis is performed using only information on the loaded class.
Japanese Unexamined Patent Application Publication No. 2003-216442 includes a code conversion unit that generates machine language code on the basis of the source code of an execution program to be processed, an optimized range determination unit that, with respect to a method in the execution program based on this machine language code, determines a range where an object created in this method is not escaping, and a scalar replacement execution unit that performs scalar replacement within the range where the object is not escaping, and discloses a technique where targets to be subjected to an escape analysis are limited.
Japanese Unexamined Patent Application Publication No. 2008-33932 relates to an improved system for recompiling code in a NUMA computer system and discloses a technique where an object which is determined in an escape analysis to be possible to allocate to the stack is placed in an area which is locally accessible by NUMA.
However, these related art examples do not suggest or disclose an escaping object to be allocated to the stack.
Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, Sam Midkiff, “Escape analysis for Java,” Proceeding OOPSLA '99 Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, ACM SIGPLAN Notices Homepage archive Volume 34 Issue 10, October 1999 (http://portal.acm.org/citation.cfm?id=320386) describes a technique for performing stack allocation using an ordinary escape analysis. However, the technique described does not allocate an object accessed by multiple workers to the stack.
Erik Corry, “Optimistic stack allocation for java-like languages,” Proceeding ISMM '06 Proceedings of the 5th international symposium on Memory management 2006 (http://portal.acm.org/citation.cfm?id=1133956.1133978) describes a technique where an object is speculatively allocated to the stack and, if the object is escaping at the point in time when the frame completes, the object is moved to the heap. However, the technology described moves an object to the heap at the point in time when the object becomes accessible by other workers, and thus move all task objects to the heap.